{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Difference Between Largest and Smallest Value in Three Moves"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minDifference"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #三次操作后最大值与最小值的最小差"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个数组&nbsp;<code>nums</code>&nbsp;。</p>\n",
    "\n",
    "<p>每次操作你可以选择&nbsp;<code>nums</code>&nbsp;中的任意一个元素并将它改成 <strong>任意值</strong> 。</p>\n",
    "\n",
    "<p>在&nbsp;<strong>执行最多三次移动后&nbsp;</strong>，返回&nbsp;<code>nums</code>&nbsp;中最大值与最小值的最小差值。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [5,3,2,4]\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>我们最多可以走 3 步。\n",
    "第一步，将 2 变为 3 。 nums 变成 [5,3,3,4] 。\n",
    "第二步，将 4 改为 3 。 nums 变成 [5,3,3,3] 。\n",
    "第三步，将 5 改为 3 。 nums 变成 [3,3,3,3] 。\n",
    "执行 3 次移动后，最小值和最大值之间的差值为 3 - 3 = 0 。</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,5,0,10,14]\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>我们最多可以走 3 步。\n",
    "第一步，将 5 改为 0 。 nums变成 [1,0,0,10,14] 。\n",
    "第二步，将 10 改为 0 。 nums变成 [1,0,0,0,14] 。\n",
    "第三步，将 14 改为 1 。 nums变成 [1,0,0,0,1] 。\n",
    "执行 3 步后，最小值和最大值之间的差值为 1 - 0 = 1 。\n",
    "可以看出，没有办法可以在 3 步内使差值变为0。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [3,100,20]\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>我们最多可以走 3 步。\n",
    "第一步，将 100 改为 7 。 nums 变成 [3,7,20] 。\n",
    "第二步，将 20 改为 7 。 nums 变成 [3,7,7] 。\n",
    "第三步，将 3 改为 7 。 nums 变成 [7,7,7] 。\n",
    "执行 3 步后，最小值和最大值之间的差值是 7 - 7 = 0。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>-10<sup>9</sup> &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-difference-between-largest-and-smallest-value-in-three-moves](https://leetcode.cn/problems/minimum-difference-between-largest-and-smallest-value-in-three-moves/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-difference-between-largest-and-smallest-value-in-three-moves](https://leetcode.cn/problems/minimum-difference-between-largest-and-smallest-value-in-three-moves/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[5,3,2,4]', '[1,5,0,10,14]', '[3,100,20]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifference(self, nums: List[int]) -> int:\n",
    "        if len(nums) < 5:\n",
    "            return 0\n",
    "        else:\n",
    "            tmp_nums, l = sorted(nums), len(nums)\n",
    "            return min([tmp_nums[l - 1] - tmp_nums[3], tmp_nums[l - 4] - tmp_nums[0], tmp_nums[l - 2] - tmp_nums[2],tmp_nums[l - 3] - tmp_nums[1]])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifference(self, nums: List[int]) -> int:\n",
    "        a1 = sorted(nums)\n",
    "        n = len(nums)\n",
    "        if n <= 4: return 0\n",
    "        if n <= 5: \n",
    "            return min(a1[1]-a1[0],a1[-1]-a1[-2],a1[-2]-a1[2],a1[-3]-a1[1])\n",
    "        return min(a1[-4]-a1[0],a1[-1]-a1[3],a1[-2]-a1[2],a1[-3]-a1[1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifference(self, nums: List[int]) -> int:\n",
    "        if len(nums) <= 4: return 0\n",
    "\n",
    "        ans = 10e12\n",
    "        n = len(nums)\n",
    "        nums = sorted(nums)\n",
    "        for i in range(4):\n",
    "            ans = min(ans, nums[i+n-4]-nums[i])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifference(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        if n < 5: return 0\n",
    "        elif n == 5:\n",
    "            ans = min(nums[i] - nums[i-1] for i in range(1, n))\n",
    "            return ans\n",
    "        else:\n",
    "            target_posi_1 = n - 3\n",
    "            i, count = 0, 3\n",
    "            while i < target_posi_1 and count > 0:\n",
    "                if nums[i] != nums[target_posi_1]:\n",
    "                    count -= 1\n",
    "                i += 1\n",
    "            if count == 0:\n",
    "                ans1 = nums[-1] - nums[i]\n",
    "            else:\n",
    "                j = n - 1\n",
    "                while j > target_posi_1:\n",
    "                    if nums[j] != nums[target_posi_1]:\n",
    "                        count -= 1\n",
    "                    if count == 0:\n",
    "                        break\n",
    "                    j -= 1\n",
    "                ans1 = nums[j-1] - nums[target_posi_1]\n",
    "            target_posi_2 = 2\n",
    "            i, count = n-1, 3\n",
    "            while i > 2 and count > 0:\n",
    "                if nums[i] != nums[target_posi_2]:\n",
    "                    count -= 1\n",
    "                i -= 1\n",
    "            if count == 0:\n",
    "                ans2 = nums[i] - nums[0]\n",
    "            else:\n",
    "                j = 0\n",
    "                while j < 2:\n",
    "                    if nums[j] != nums[target_posi_2]:\n",
    "                        count -= 1\n",
    "                    if count == 0:\n",
    "                        break\n",
    "                    j += 1\n",
    "                ans2 = nums[target_posi_2] - nums[j+1]\n",
    "            return min(ans1, ans2, nums[-2] - nums[2], nums[-3] - nums[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifference(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n <= 4:\n",
    "            return 0\n",
    "        nums.sort()\n",
    "        res = min(nums[n-4+i] - nums[i] for i in range(4))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifference(self, nums: List[int]) -> int:\n",
    "        # greedy return local best\n",
    "        # this problem requires global best\n",
    "        # global != local\n",
    "        nums.sort()\n",
    "        l = len(nums)\n",
    "        if l <= 4:  return 0\n",
    "        res = float('inf')\n",
    "        for i in range(4):\n",
    "            tmp = nums[-4 + i] - nums[i]\n",
    "            res = min(res, tmp)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifference(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        if n<=3:\n",
    "            return 0\n",
    "        nums.sort()\n",
    "        return min(nums[-1]-nums[3],nums[-2]-nums[2],nums[-3]-nums[1],nums[-4]-nums[0])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifference(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        if len(nums)<=4:\n",
    "            return 0\n",
    "        else:\n",
    "            n=len(nums)\n",
    "            #找剩下的任意n-3个数中,最大值与最小值的差的最小值\n",
    "            c=inf\n",
    "            for i in range(4):\n",
    "                c=min(c,nums[i+n-4]-nums[i])\n",
    "            return c\n",
    "\n",
    "            # 0,1,1,4,6,6,6"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifference(self, nums: List[int]) -> int:\n",
    "        if len(nums) <= 4:\n",
    "            return 0\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        return min(nums[n-4 + i] - nums[i] for i in range(4))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minDifference(self, nums: List[int]) -> int:\r\n",
    "        # 可以把任意3个变成剩余的元素, 最小值一定是0\r\n",
    "        if len(nums) <= 4: return 0\r\n",
    "        nums.sort()\r\n",
    "        # 依次对应四种方案: 去除最小3个/去除最小2个和最大1个/去除最小1个和最大2个/去除最大3个\r\n",
    "        return min(nums[-1] - nums[3], nums[-2] - nums[2], nums[-3] - nums[1],\r\n",
    "                   nums[-4] - nums[0])\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifference(self, nums: List[int]) -> int:\n",
    "        if len(nums) < 4:\n",
    "            return 0\n",
    "        else:\n",
    "            nums.sort()\n",
    "            diff = nums[-1] - nums[0]\n",
    "            for i in range(4):\n",
    "                cur_diff = nums[-(4-i)] - nums[i]\n",
    "                diff = min(diff, cur_diff)\n",
    "            return diff"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifference(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        print(nums)\n",
    "        if len(nums)<=4: return 0\n",
    "        ans=inf\n",
    "        for k in range(4):\n",
    "            ans=min(ans,nums[k-4]-nums[k])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifference(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n <= 4: return 0\n",
    "        nums.sort()\n",
    "        res = float('inf')\n",
    "        for i in range(4):\n",
    "            res = min(res, nums[n-4+i] - nums[i])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifference(self, nums: List[int]) -> int:\n",
    "        if len(nums) <= 4: return 0\n",
    "\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        ret = min(nums[n - 4 + i] - nums[i] for i in range(4))\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifference(self, nums: List[int]) -> int:\n",
    "        if len(nums) <= 4:\n",
    "            return 0\n",
    "        nums.sort()\n",
    "        ans = inf\n",
    "        for i in range(4):\n",
    "            ans = min(ans, nums[-1-i] - nums[3-i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifference(self, nums: List[int]) -> int:\n",
    "        if len(nums)<=4:\n",
    "            return 0\n",
    "        if len(nums)==5:\n",
    "            nums.sort()\n",
    "            min1=nums[1]-nums[0]\n",
    "            for i in range(3):\n",
    "                if nums[i+2]-nums[i+1]<min1:\n",
    "                    min1=nums[i+2]-nums[i+1]\n",
    "            return min1\n",
    "        nums.sort()\n",
    "        label=nums[-1]-nums[0]\n",
    "        for i in range(4):\n",
    "            a=nums[i:4]\n",
    "            b=b=nums[-4:len(nums)-3+i]\n",
    "            label=min(label, b[-1]-a[0])\n",
    "        return label\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifference(self, nums: List[int]) -> int:\n",
    "        # 只能修改3个数字，其实就是去找任意n-3个数字的最小差距\n",
    "        # 排序后，计算 n-3 长度的窗口的最大值与最小值差距\n",
    "        n = len(nums)\n",
    "        if n<=4:\n",
    "            return 0\n",
    "        nums.sort()\n",
    "        min_diff = float('inf')\n",
    "        L = n-3\n",
    "        for i in range(0,n-L+1):\n",
    "            l,r = i,i+L-1\n",
    "            min_diff = min(min_diff, nums[r]-nums[l])\n",
    "        return min_diff"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifference(self, nums: List[int]) -> int:\n",
    "        if len(nums) <= 3:\n",
    "            return 0\n",
    "\n",
    "        nums.sort()\n",
    "\n",
    "        return min(nums[-4] - nums[0], nums[-3] - nums[1], nums[-2] - nums[2], nums[-1] - nums[3])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifference(self, nums: List[int]) -> int:\n",
    "        if len(nums) <= 4:\n",
    "            return 0\n",
    "        \n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        ret = min(nums[n - 4 + i] - nums[i] for i in range(4))\n",
    "        return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifference(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        if len(nums)<=4:\n",
    "            return 0 \n",
    "        window_length = len(nums)-3-1\n",
    "        smalles_gap   = math.inf\n",
    "        for i in range(len(nums)-window_length):\n",
    "            if nums[i+window_length]-nums[i] < smalles_gap:\n",
    "                smalles_gap = nums[i+window_length]-nums[i]\n",
    "        return smalles_gap\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifference(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        if n <= 3:\n",
    "            return 0\n",
    "        result = float(\"inf\")\n",
    "        for i in range(4):\n",
    "            result = min(result, nums[n-4+i] - nums[i])\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifference(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        if len(nums)<=4:\n",
    "            return 0 \n",
    "        window_length = len(nums)-3-1\n",
    "        smalles_gap   = math.inf\n",
    "        for i in range(len(nums)-window_length):\n",
    "            if nums[i+window_length]-nums[i] < smalles_gap:\n",
    "                smalles_gap = nums[i+window_length]-nums[i]\n",
    "        return smalles_gap\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifference(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n=len(nums)\n",
    "        if n<=3:\n",
    "            return 0\n",
    "        return min(nums[n-1]-nums[3],nums[n-2]-nums[2],nums[n-3]-nums[1],nums[n-4]-nums[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifference(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        if n <= 4:\n",
    "            return 0\n",
    "        return min(nums[-1]-nums[3], nums[-2]-nums[2], nums[-3]-nums[1], nums[-4]-nums[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifference(self, nums: List[int]) -> int:\n",
    "        length = len(nums)\n",
    "        if length < 5:\n",
    "            return 0\n",
    "\n",
    "        res = inf\n",
    "\n",
    "        nums.sort()\n",
    "\n",
    "        res = min(res, nums[-1] - nums[3])\n",
    "        res = min(res, nums[-2] - nums[2])\n",
    "        res = min(res, nums[-3] - nums[1])\n",
    "        res = min(res, nums[-4] - nums[0])\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minDifference(self, nums: List[int]) -> int:\r\n",
    "        ####最省事的办法。排序。枚举可能的情况\r\n",
    "        n = len(nums)\r\n",
    "        if n <= 4:\r\n",
    "            return 0\r\n",
    "        \r\n",
    "        nums.sort()\r\n",
    "\r\n",
    "        res = float('inf')\r\n",
    "        for i in range(4):\r\n",
    "            res = min(res, nums[n-1-i] - nums[(3-i)])\r\n",
    "\r\n",
    "        return res\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifference(self, nums: List[int]) -> int:\n",
    "        if len(nums) <= 4:\n",
    "            return 0\n",
    "        nums.sort()\n",
    "        ans = inf\n",
    "        for i in range(4):\n",
    "            ans = min(ans, nums[-4 + i] - nums[i])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifference(self, nums: List[int]) -> int:\n",
    "        # 可以把任意3个变成剩余的元素, 最小值一定是0\n",
    "        if len(nums) <= 4: return 0\n",
    "        nums.sort()\n",
    "        # 依次对应四种方案: 去除最小3个/去除最小2个和最大1个/去除最小1个和最大2个/去除最大3个\n",
    "        return min(nums[-1] - nums[3], nums[-2] - nums[2], nums[-3] - nums[1],\n",
    "                   nums[-4] - nums[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifference(self, nums: List[int]) -> int:\n",
    "        if len(nums)<5: return 0\n",
    "        nums.sort()\n",
    "        mx=nums[-4]-nums[0]\n",
    "        mx=min(mx,nums[-3]-nums[1])\n",
    "        mx=min(mx,nums[-2]-nums[2])\n",
    "        mx=min(mx,nums[-1]-nums[3])\n",
    "        return mx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifference(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n < 5:\n",
    "            return 0\n",
    "        nums.sort()\n",
    "        return min(nums[-1] - nums[3], nums[n - 4] - nums[0], nums[n - 3] - nums[1], nums[n - 2] - nums[2], nums[n - 1] - nums[3])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifference(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        if n<=3:\n",
    "            return 0\n",
    "        nums.sort()\n",
    "        return min(nums[-1]-nums[3],nums[-2]-nums[2],nums[-3]-nums[1],nums[-4]-nums[0])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def minDifference(self, nums: List[int]) -> int:\n",
    "        if len(nums) < 4:\n",
    "            return 0\n",
    "            \n",
    "        min_items = heapq.nsmallest(4, nums)\n",
    "        max_items = heapq.nlargest(4, nums)\n",
    "        max_items.sort()\n",
    "\n",
    "        return min([(max_items[i] - min_items[i]) for i in range(4)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifference(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        if len(nums)<=4:\n",
    "            return 0\n",
    "        else:\n",
    "            n=len(nums)\n",
    "            #找剩下的任意n-3个数中,最大值与最小值的差的最小值\n",
    "            c=inf\n",
    "            for i in range(4):\n",
    "                c=min(c,nums[i+n-4]-nums[i])\n",
    "            return c\n",
    "\n",
    "            # 0,1,1,4,6,6,6"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifference(self, nums: List[int]) -> int:\n",
    "        if len(nums) <= 4:\n",
    "            return 0\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        ret = min(nums[n - 4 + i] - nums[i] for i in range(4))\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifference(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        if len(nums)<=4:\n",
    "            return 0\n",
    "        print(nums)    \n",
    "        return min(nums[-4]-nums[0],nums[-3]-nums[1],nums[-2]-nums[2],nums[-1]-nums[3])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifference(self, nums: List[int]) -> int:\n",
    "        if len(nums) <= 4:\n",
    "            return 0\n",
    "        \n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        ret = min(nums[n - 4 + i] - nums[i] for i in range(4))\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifference(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n < 5:\n",
    "            return 0\n",
    "        nums.sort()\n",
    "        # 滑动4次的窗口，窗口大小为n-3，增量为n-4\n",
    "        add = n - 4\n",
    "        return min(nums[i + add] - nums[i] for i in range(4))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifference(self, nums: List[int]) -> int:\n",
    "\n",
    "        if(len(nums) <= 4):\n",
    "            return 0\n",
    "\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        print(nums)\n",
    "        ret = float('inf')\n",
    "        for i in range(4):\n",
    "            ret = min(ret, nums[n -4 + i] - nums[i])\n",
    "\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifference(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n < 5:\n",
    "            return 0\n",
    "        nums.sort()\n",
    "        # 滑动4次的窗口，窗口大小为n-3，增量为n-4\n",
    "        add = n - 4\n",
    "        return min(nums[i + add] - nums[i] for i in range(4))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifference(self, nums: List[int]) -> int:\n",
    "        if len(nums) <= 4:\n",
    "            return 0\n",
    "\n",
    "        n = len(nums)\n",
    "        maxn = [-10**9] * 4\n",
    "        minn = [10**9] * 4\n",
    "\n",
    "        for i in range(n):\n",
    "            add = 0\n",
    "            while add < 4 and maxn[add] > nums[i]:\n",
    "                add += 1\n",
    "            if add < 4:\n",
    "                maxn[add:] = [nums[i]] + maxn[add:-1]\n",
    "            \n",
    "            add = 0\n",
    "            while add < 4 and minn[add] < nums[i]:\n",
    "                add += 1\n",
    "            if add < 4:\n",
    "                minn[add:] = [nums[i]] + minn[add:-1]\n",
    "        \n",
    "        print(minn, maxn)\n",
    "        ret = min(maxn[i] - minn[3 - i] for i in range(4))\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifference(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        l = len(nums)\n",
    "        if l <= 4:  return 0\n",
    "        res = float('inf')\n",
    "        for i in range(4):\n",
    "            tmp = nums[-4 + i] - nums[i]\n",
    "            res = min(res, tmp)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifference(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n <= 4:\n",
    "            return 0\n",
    "        nums.sort()\n",
    "        # print(f'{nums}')\n",
    "        ret = min(nums[n - 4 + i] - nums[i] for i in range(4))\n",
    "        return ret\n",
    "\n",
    "        # 0 1 5 10 14"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifference(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n<=4:\n",
    "            return 0\n",
    "        nums.sort()\n",
    "        min_diff = float('inf')\n",
    "        L = n-3\n",
    "        for i in range(0,n-L+1):\n",
    "            l,r = i,i+L-1\n",
    "            min_diff = min(min_diff, nums[r]-nums[l])\n",
    "        return min_diff"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifference(self, nums: List[int]) -> int:\n",
    "        # n = len(nums)\n",
    "        # if n <= 4:\n",
    "        #     return 0\n",
    "        # nums.sort()\n",
    "        # return min(nums[-4] - nums[0], nums[-3] - nums[1], nums[-2] - nums[2], nums[-1] - nums[3])\n",
    "        n = len(nums)\n",
    "        if n <= 4:\n",
    "            return 0\n",
    "        maxn = [-inf] * 4\n",
    "        minn = [inf] * 4\n",
    "        for i in range(n):\n",
    "            add = 0\n",
    "            while add < 4 and maxn[add] > nums[i]:\n",
    "                add += 1\n",
    "            if add < 4:\n",
    "                maxn[add:] = [nums[i]] + maxn[add:-1]\n",
    "            \n",
    "            add = 0\n",
    "            while add < 4 and minn[add] < nums[i]:\n",
    "                add += 1\n",
    "            if add < 4:\n",
    "                minn[add:] = [nums[i]] + minn[add:-1]\n",
    "            \n",
    "        return min(maxn[i] - minn[3-i] for i in range(4))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifference(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n <= 4:\n",
    "            return 0\n",
    "        nums.sort()\n",
    "        return min(nums[-4] - nums[0], nums[-3] - nums[1], nums[-2] - nums[2], nums[-1] - nums[3])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifference(self, nums: List[int]) -> int:\n",
    "        if len(nums) <= 4:  return 0\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        return min(nums[n-4]-nums[0], nums[n-3]-nums[1], nums[n-2]-nums[2], nums[n-1]-nums[3])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minDifference(self, nums: List[int]) -> int:\r\n",
    "        n = len(nums)\r\n",
    "        if n <= 4:\r\n",
    "            return 0\r\n",
    "        \r\n",
    "        nums.sort()\r\n",
    "\r\n",
    "        res = float('inf')\r\n",
    "        for i in range(4):\r\n",
    "            res = min(res, nums[n-1-i] - nums[(3-i)])\r\n",
    "\r\n",
    "        return res\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifference(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        print(nums)\n",
    "        if len(nums)<=4: return 0\n",
    "        ans=inf\n",
    "        for k in range(4):\n",
    "            ans=min(ans,nums[k-4]-nums[k])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifference(self, nums: List[int]) -> int:\n",
    "        if len(nums) <= 4:\n",
    "            return 0\n",
    "        \n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        ret = min(nums[n - 4 + i] - nums[i] for i in range(4))\n",
    "        return ret"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
